class Solution:
    # 翻转一个子链表，并且返回新的头与尾
    def reverse(self, head: ListNode, tail: ListNode):
        prev = tail.next
        p = head
        while prev != tail:
            nex = p.next
            # prev是在后面位置的,所以要指向原来的方向
            p.next = prev
            prev = p
            p = nex
        return tail, head

    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        hair = ListNode(0)
        hair.next = head
        pre = hair

        while head:
            tail = pre
            # 查看剩余部分长度是否大于等于 k
            for i in range(k):
                tail = tail.next
                if not tail:
                    return hair.next
            nex = tail.next
            head, tail = self.reverse(head, tail)
            # 把子链表重新接回原链表
            pre.next = head
            tail.next = nex

            pre = tail
            head = tail.next

        return hair.next
'''
因此，在翻转子链表的时候，我们不仅需要子链表头结点 head，还需要有 head 的上一个结点 pre，以便翻转完后把子链表再接回 pre。

但是对于第一个子链表，它的头结点 head 前面是没有结点 pre 的。太麻烦了！难道只能特判了吗？答案是否定的。没有条件，我们就创造条件；没有结点，我们就创建一个结点。我们新建一个结点，把它接到链表的头部，让它作为 pre 的初始值，这样 head 前面就有了一个结点，我们就可以避开链表头部的边界条件。这么做还有一个好处，下面我们会看到。

反复移动指针 head 与 pre，对 head 所指向的子链表进行翻转，直到结尾，我们就得到了答案。下面我们该返回函数值了。

有的同学可能发现这又是一件麻烦事：链表翻转之后，链表的头结点发生了变化，那么应该返回哪个结点呢？照理来说，前 k 个结点翻转之后，链表的头结点应该是第 k 个结点。那么要在遍历过程中记录第 k 个结点吗？但是如果链表里面没有 k 个结点，答案又还是原来的头结点。我们又多了一大堆循环和判断要写，太崩溃了！

等等！还记得我们创建了节点 pre吗？这个结点一开始被连接到了头结点的前面，而无论之后链表有没有翻转，它的 next 指针都会指向正确的头结点。那么我们只要返回它的下一个结点就好了。至此，问题解决。

'''
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # 翻转一个子链表，并且返回新的头与尾
    def reverse(self, head: ListNode, tail: ListNode):
        p = head
        prev = None
        while prev != tail:
            nex = p.next
            p.next = prev
            prev = p
            # 易错点!
            p = nex
        return tail, head

    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        hair = ListNode(0)
        hair.next = head
        pre = hair
        while head:
            tail = pre
            # 将tail移到尾部
            for i in range(k):
                tail = tail.next
                if not tail:
                    return hair.next
            # 反转链表, 先保存nex,是tail.next!!!!
            nex = tail.next
            # 反转完之后tail, head = head, tail
            head, tail = self.reverse(head,tail)

            # 重建连接
            pre.next = head
            tail.next = nex
            # 下一个k, pre和head两个指针
            pre = tail
            head = tail.next
        return hair.next